Computations may be carried out within a computer under a variety of number coding systems, including simple binary coded (SBC) systems and binary coded decimal (BCD) systems.
In simple binary coded (SBC) numbering, the decimal numbers zero through fifteen are represented by the 4-bit code series, 0000, 0001, 0010, . . . , 1110, 1111. Simple binary coded (SBC) numbering is generally preferred for carrying out arithmetic computations since this representation of decimal numbers enable basic digital circuit components to perform basic arithmetic operations in the same manner as decimal operations are performed.
In a binary coded decimal (BCD) numbering system, the decimal digits, zero through nine, are also represented by a 4-bit code series, 0000, 0001, 0010, . . . , 1000, 1001. But the remaining 4-bit binary codes, 1010 through 1111 of the sequence, have no digital numerical meaning, instead, numbers in the range ten through fifteen are represented by two 4-bit codes (two digits), as are all further numbers up to and including ninety-nine.
Because of this lack in continuity in decimal (BCD) numbering, certain operations result in meaningless or erroneous results. For instance, a one-bit shift-left operation on a binary coded decimal six (represented by the bit series: 0000, 0110) does not produce a binary coded decimal twelve (represented by the bit series: 0001, 0010). Instead, it produces a bit series (0000 1100) which has no meaning in the domain of binary coded decimal numbers. Similarly, a one-bit shift-right operation on a binary coded decimal twelve (represented by the bit series 0001 0010) does not produce a BCD representation of a digital six but rather a bit series (0000 1001) which represents a digital nine in the BCD numbering system.
As a result of resulting calculation errors caused by the discontinuity in the binary meaning of certain digital calculations, a different and more complex set of bit-manipulation rules have to be followed within a digital computer for performing arithmetic operations such as addition, subtraction, multiplication and division of binary coded decimal (BCD) numbers, Despite these difficulties, there are instances where it is advantageous to carry out arithmetic computations directly on BCD numbers without transforming the BCD numbers into simple binary coded numbers, particularly where data are stored in the BCD format.
When multiplication and division operations are to be carried out directly on BCD formatted numbers, it is advantageous to be able to quickly generate signals representing the one-times (×1) through nine-times (×9) multiples of every multidigit BCD (binary coded decimal) number that can be represented by a predefined number of bits (e.g., 64 bits). If a first BCD number (multiplicand) is to be multiplied by a second BCD number (multiplier), the final product is typically generated by adding shifted multiples of the multiplicand. These multiples are commonly referred to as “partial products.” Each partial product is equal to the product of the multiplicand and a corresponding single digit within the multiplier.
Previous approaches to generating multiples of a BCD multiplicand consume either excessive amounts of computer time or an excessive amount of circuit real estate. Particularly time consuming is the generation of the multiple for use as a partial product to be added to other partial products in certain fixed point or floating point multiplying. The problem is that generating the multiple can be time consuming.
Various approaches to solving this problem are summarized in the paper by Alvaro V'azquez, Elisardo Antelo and Paolo Montuschi, entitled; “A New Family of High-Performance Parallel Decimal Multipliers”, 18th IEEE Symposium on Computer Arithmetic, June 2007, which shows a multiplicand triple being developed by converting from BCD-8421 to BCD-4221. A. Yamaoka and K. Wada and K. Kuriyama's “Decimal Multiplier Device and Method Therfor”, U.S. Pat. No. 4,745,569, May 1998 showed a multiplicand triple being developed by successive additions of the multiplicand. T. Ueda, “Decimal Multiplying Assembly and Multiple Module” U.S. Pat. No. 5,379,245, January 1995 shows a multiplicand triple being developed by examining a digit of the multiplicand, a digit of the multiplier, and any incoming carry or carries.
One approach involves generating a double of the multiplicand, and then adding the multiplicand to that doubled amount via a carry-propagate addition. However, a carry propagate addition is time consuming and with 34-digit, and even 16-digit operands (these two operand lengths being suggested by the recently approved IEEE Standard on Floating-Point Arithmetic—P754-2008), such addition can be a cycle-limiting factor.